package 力扣._239滑动窗口最大值;

import java.util.Arrays;
import java.util.PriorityQueue;

public class Solution2 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] r = new int[nums.length + 1 - k];
        //优先队列, 值大的在前，值相同时下标小的在前（这样优先把不属于窗口的出队）
        PriorityQueue<int[]> queue = new PriorityQueue<>(((o1, o2) -> o2[0] != o1[0] ? o2[0] - o1[0] : o1[1] - o2[1]));
        for (int i = 0; i < k; i++) {
            queue.add(new int[]{nums[i], i});
        }
        for (int i = k; i <= nums.length; i++) {
            while (!queue.isEmpty() && queue.peek()[1] < i - k) queue.poll();
            r[i - k] = queue.peek()[0];
            if (i < nums.length)
                queue.add(new int[]{nums[i], i});
        }
        r[r.length - 1] = queue.peek()[0];
        return r;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, -1};
        int k = 1;
        int[] ints = new Solution2().maxSlidingWindow(nums, k);
        System.out.println(Arrays.toString(Arrays.stream(ints).toArray()));
    }
}
